from typing import List


class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        fresh = 0
        q = []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append((i, j)) # 一开始就腐烂的橘子
                elif grid[i][j] == 1:
                    fresh += 1 # 统计新鲜橘子个数
        minute = 0
        while q and fresh:
            minute += 1
            tmp = q
            q = []
            for x, y in tmp:  # 已经腐烂的橘子
                for i, j in (x, y-1), (x, y+1), (x-1, y), (x+1, y):
                    if 0 <= i < m and 0 <= j < n and grid[i][j] == 1 :# 新鲜橘子
                        fresh -= 1
                        grid[i][j] = 2
                        q.append((i, j))
        return -1 if fresh else minute



            